package com.ztl.leetcode.SwordFingerOffer;

/**
 * @author @ztl
 * @ClassName:DeleteListNode_18
 * @Package:com.ztl.leetcode.SwordFingerOffer
 * @date 2023年05月15日 20:30
 * @description: 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
 * 返回删除后的链表的头节点。
 * @version: 1.0
 */
public class DeleteListNode_18 {
    //需要遍历一次链表，时间复杂度O(n),使用常数大小空间存储数据，空间复杂度O(1)
    public ListNode deleteNode(ListNode head, int val) {
        //思路：使用双指针一前一后遍历链表，未发现目标时前后指针共同前进一步，发现目标时将后指针指向前指针的next；
        //最后返回后指针的头节点即可

        //定义list为后指针的起始位置
        ListNode list = new ListNode(-1);
        //为保留后指针起始位置，使用temp临时指针操作后指针链表
        ListNode temp = list;

        //开始循环遍历链表
        while(head!=null){
            //当前指针找到目标时，后指针跳过该目标，也就是后指针的next直接指向前指针的next
            if(head.val == val) {
                temp.next = head.next;
                break; //删除节点完成，直接退出循环
            }else{
                //否则将后指针next指向前指针，这里是为了第一次循环时给后指针链接到head
                temp.next = head;

            }
            //没有找到目标，前后指针一起前进
            temp = temp.next;
            head = head.next;
        }

        //最后返回起始位置的next，也就是不包含val的链表
        return list.next;
    }
}
